Gaga cover ca khúc "Orange Colored Sky" trong một lần xuất hiện bất ngờ tại nhà hàng Oak Room, tọa lạc tại Thành phố New York vào ngày 29 tháng 9 năm 2010 và lần thứ hai vào ngày 5 tháng 1 năm 2011.[1] Nghệ sĩ Brian Newan đóng vai trò là nghệ sĩ khách mời biểu diễn kèn trumpet cho các màn trình diễn tại sự kiện Robin Hood Gala vào ngày 9 tháng 5 năm 2011 với mục đích hỗ trợ gây quỹ cho tổ chức Robin Hood Foundation và tại sự kiện âm nhạc BBC Radio 1's Big Weekend tổ chức ở Carlisle, Anh vào ngày 15 tháng 5 cùng năm.[2] Sau này trên chương trình đặc biệt A Very Gaga Thanksgiving phát sóng trên kênh ABC nhân dịp ngày Lễ Tạ ơn, Gaga tiếp tục cover lại ca khúc[3] cùng với một bản cover ca khúc "White Christmas". Ngoài việc nhấn mạnh cái bản chất jazz của "White Christmas" cho khán giả chiêm ngưỡng thì cô còn tự thêm phần lời thứ hai cho nó vì cho rằng bài hát gốc "ngắn quá". Trong đoạn lời của mình, nữ ca sĩ miêu tả một chú người tuyết và nói rằng Ông già Noel đang trên đường đến gặp chú. Đoạn lời kết thúc sau khi Gaga nói "Thôi được rồi, thế thì tôi phải thừa nhận là ngoài trời tuyết rơi chưa dày lắm đâu."[4] Các ca khúc thuộc A Very Gaga Holiday được thu âm trong khoảng thời gian chương trình A Very Gaga Thanksgiving đang trong quá trình ghi hình tại trường nữ sinh Convent of the Sacred Heart, Thành phố New York.[5]

Ngày 22 tháng 11 năm 2011, A Very Gaga Holiday chính thức ra mắt công chúng dưới dạng EP nhạc số. Cả hai bản cover "Orange Colored Sky", "White Christmas" và hai ca khúc khác gồm các phiên bản acoustic của các đĩa năm 2011 của Gaga là "The Edge of Glory" và "You and I" – là cả hai ca khúc nằm trong album phòng thu thứ hai của nữ ca sĩ với tựa đề Born This Way – đều được đưa vào EP.[6] Hãng thu âm Interscope Records thông báo về EP sau buổi khai trương của xưởng thủ công Holiday Wonderland Gaga Workshop trong trung tâm cửa hàng bách hóa Barneys New York.[4] A Very Gaga Holiday chính thức được mở bán tại Hoa Kỳ trên iTunes Store và Amazon rồi được phát hành trên toàn cầu vào bốn ngày sau đó.[6][7]